დინამიკური პროგრამირება.
მარიამ გობრონიძე

ტექსტის გადანაწილება - Text Justification
მოცემულია სტრინგების მასივი words და სიგანე maxWidth. დააფორმატეთ ტექსტი ისე, რომ
თითოეულ ხაზს ზუსტად maxWidth სიმბოლო ჰქონდეს და იყოს სრულად — როგორც
მარცხენა, ისე მარჯვენა მხარეს — გასწორებული (Justified).
ტექსტის განაწილება უნდა შესრულდეს greedy მიდგომით; ანუ, თითოეულ ხაზში ჩასვით რაც
შეიძლება მეტი სიტყვა. აუცილებლობის შემთხვევაში, ხაზზე დარჩენილი ადგილი შეავსეთ
დამატებითი ცარიელი სიმბოლოებით ' ', რათა ხაზის სიგრძე ზუსტად შეესაბამებოდეს
maxWidth-ს.

ტექსტის გადანაწილება - Text Justification
ხაზზე არსებული დამატებითი სივრცეები უნდა განაწილდეს სიტყვებს შორის რაც შეიძლება
თანაბრად. იმ შემთხვევაში, თუ სივრცეების რაოდენობა არ იყოფა თანაბრად სიტყვათა შორის
არსებულ ცარიელ ადგილებზე, მაშინ მარცხენა მხარეს მყოფ ცარიელ ადგილებს უნდა
მიენიჭოს მეტი ცარიელი სიმბოლო, ვიდრე მარჯვენას.
ბოლო ხაზი უნდა იყოს მარცხნივ გასწორებული (left-justified), და მასზე სიტყვებს შორის არ
უნდა ჩაისვას ზედმეტი ცარიელი სიმბოლო.

შენიშვნები
●

სიტყვად ითვლება სიმბოლოების თანმიმდევრობა, რომელიც არ შეიცავს ცარიელ
სივრცეებს.

●

თითოეული სიტყვის სიგრძე გარანტირებულად მეტია 0-ზე და არ აღემატება maxWidthს.

●

მასივ words-ში სულ მცირე ერთი სიტყვა მაინც არის.

სირთულის შეფასება
დროითი სირთულე: O(N*MaxWidth)
მეხსიერებითი სირთულე: O(N*MaxWidth)

House Robber
მოცემულია n სახლი , რომლებიც ერთ ხაზზეა აშენებული. თითოეულ სახლში ინახება
გარკვეული რაოდენობის ფული. მძარცველს სურს მოიპაროს სახლებში არსებული თანხა,
მაგრამ მას არ შეუძლია ორი მეზობელი სახლიდან ერთდროულად ქურდობა .
ამოცანაა – განსაზღვროთ მაქსიმალური რაოდენობის ფული, რომლის მოპარვაც მძარცველს
შეუძლია მოცემული შეზღუდვის გათვალისწინებით.

ნაივური მიდგომა
იდეა მდგომარეობს იმაში, რომ რეკურსიის მეშვეობით გამოვიკვლიოთ ყველა შესაძლო
ვარიანტი თითოეული სახლისთვის . შეგვიძლია დავიწყოთ ბოლო სახლიდან და თითოეული
სახლისთვის გავითვალისწინოთ ორი არჩევანი:
1.

გავძარცვოთ მიმდინარე სახლი და გამოვტოვოთ მის მეზობელი (წინა ) სახლი .

2.

გამოვტოვოთ მიმდინარე სახლი და გადავინაცვლოთ მომდევნოში.

რეკურსიული დამოკიდებულება
maxLootRec(n) = max(hval[n - 1] + maxLootRec(n - 2), maxLootRec(n 1))

სირთულის შეფასება
დროითი სირთულე: O(2^n)
მეხსიერებითი სირთულე: O(n)

Using Memoization - O(n) Time and O(n)
Space

ზემოთ მოცემულ ამოხსნას აქვს ოპტიმალური ქვესტრუქტურა და გადაფარვადი
ქვეამოცანები . იხილე ქვემოთ მოცემული რეკურსიის ხე – მაგალითად, maxLootRec(2)
ორჯერ განიხილება:
რეკურსიის ხე – House Robber ამოცანისთვის

ამ გადაწყვეტილების ოპტიმიზაცია შესაძლებელია მეხსიერების მასივის (memo array)
დახმარებით, რომლის სიგრძეც იქნება (n + 1).
ამ მასივში memo[i] აღნიშნავს მაქსიმალურ თანხას , რომლის მოპარვაც შესაძლებელია
პირველი i სახლიდან .
გაითვალისწინე, რომ რეკურსიაში იცვლება მხოლოდ ერთი პარამეტრი, ხოლო ამ პარამეტრის
დიაპაზონი არის 0-დან n-მდე.

Using Tabulation - O(n) Time and O(n)
Space

იდეა მდგომარეობს იმაში, რომ ამოხსნა ავაგოთ bottom-up მიდგომით .
ვქმნით dp[] მასივს ზომით n + 1, სადაც dp[i] აღნიშნავს მაქსიმალურ თანხას , რომლის
მოპარვაც შესაძლებელია პირველი i სახლიდან .
პირველ რიგში ვავსებთ უკვე ცნობილ მნიშვნელობებს: dp[0] და dp[1],
შემდეგ კი ვავსებთ დარჩენილ მნიშვნელობებს შემდეგი ფორმულის გამოყენებით:
dp[i] = max(hval[i-1] + dp[i - 2], dp[i - 1])

Space-Optimized DP - O(n) Time and O(1)
Space

წინა მიდგომაში გამოყენებულ dp[] მასივზე დაკვირვებისას შეიმჩნევა, რომ მიმდინარე
ინდექსზე მიღებული პასუხი დამოკიდებულია მხოლოდ წინა ორ მნიშვნელობაზე. სხვა
სიტყვებით, dp[i] დამოკიდებულია მხოლოდ dp[i - 1]-სა და dp[i - 2]-ზე.
ამიტომ, მთელი მასივის შენახვის ნაცვლად, შეგვიძლია უბრალოდ ორი ცვლადი გამოვიყენოთ
— ერთში შევინახოთ წინა მნიშვნელობა, მეორეში კი წინის წინა შედეგი.

Word Break
მოცემულია სტრინგი s და n სიტყვიანი ლექსიკონი dictionary. უნდა შეამოწმოთ,
შესაძლებელია თუ არა სტრინგი s დავყოთ სიტყვებად, ისე რომ თითოეული ნაწილი იყოს
ლექსიკონში არსებული სწორი სიტყვა და ისინი გამოყოფილნი იყვნენ გამოტოვებით (space).

Using Recursion - O(2^n) Time and O(n)
Space

იდეა
იდეა მდგომარეობს იმაში, რომ თითოეული პრეფიქსი (სტრიქონის დასაწყისი ნაწილი)
განვიხილოთ ცალკე და ვეძებოთ ის ლექსიკონში.
თუ პრეფიქსი არსებობს ლექსიკონში, მაშინ რეკურსიულად ვამოწმებთ დარჩენილი
სტრიქონის (ანუ სუფიქსის) არსებობას ტექსტში.
თუ სუფიქსისთვის რეკურსიული გამოძახება აბრუნებს true-ს, მაშინ საბოლოოდ ვაბრუნებთ
true.
წინააღმდეგ შემთხვევაში, ვცდით შემდეგ პრეფიქსს.
თუ ყველა შესაძლო პრეფიქსი ვცადეთ და ვერც ერთმა მათგანმა ვერ გამოიღო შედეგი, მაშინ
ვაბრუნებთ false.

Using Top-Down DP - O(n^2) Time and
O(n+m) Space

იდეა
იდეა მდგომარეობს იმაში, რომ რეკურსიულ ამოხსნაში გამოვიყენოთ დინამიკური
პროგრამირება , რათა თავიდან ავიცილოთ ერთი და იგივე ქვეამოცანების ხელახალი
გამოთვლა.
დროითი სირთულის კიდევ უფრო ოპტიმიზაციისთვის, ლექსიკონში არსებული სიტყვები
გადავიტანოთ set-ში, რაც გააუმჯობესებს სიტყვების ძიების სისწრაფეს O(m)-დან O(1)მდე.
თუ ყურადღებით დავაკვირდებით, დავინახავთ, რომ ზემოაღნიშნული რეკურსიული ამოხსნა
აკმაყოფილებს დინამიკური პროგრამირების ორ ძირითად თვისებას:

1. ოპტიმალური ქვესტრუქტურა (Optimal Substructure):
იმის შესამოწმებლად, შესაძლებელია თუ არა სტრინგის გაყოფა i ინდექსიდან დაწყებული, ანუ
ფუნქცია wordBreakRec(i), დამოკიდებულია ქვეამოცანის გადაწყვეტილებებზე
wordBreakRec(j) (სადაც j მერყეობს i-დან n-მდე).
დავაბრუნოთ true, თუკი s[i:j] არის ლექსიკონში და wordBreakRec(j) ასევე აბრუნებს
true-ს.

2. გადაფარვადი ქვეამოცანები (Overlapping Subproblems):
რეკურსიული მიდგომის გამოყენებისას ვამჩნევთ, რომ ზოგიერთი ქვეამოცანა არაერთხელ
გამოითვლება.
მაგალითად: wordBreakRec(0) გამოიძახებს wordBreakRec(1)-სა და
wordBreakRec(2)-ს. თავის მხრივ, wordBreakRec(1) ისევ გამოიძახებს
wordBreakRec(2)-ს.

რადგან ამ ამოხსნაში იცვლება მხოლოდ ერთი პარამეტრი — ინდექსი i, შეგვიძლია
გამოვიყენოთ ერთ განზომილებიანი მასივი (1D array) ზომით n, მემორიზაციისთვის.
საწყის ეტაპზე მასივი შევავსოთ -1-ებით, რაც მიანიშნებს, რომ ჯერ არცერთი მნიშვნელობა არ
არის გამოთვლილი.
შემდეგ ვცვლით რეკურსიულ ამოხსნას ისე, რომ პირველ რიგში შევამოწმოთ, უკვე
გამოთვლილია თუ არა მნიშვნელობა (-1 ნიშნავს არა). მხოლოდ ამის შემდეგ ვაკეთებთ
რეკურსიულ გამოძახებებს.
ასე, თავიდან ვირიდებთ ერთი და იგივე ქვეპრობლემის ხელახალ გამოთვლას.

Using Bottom Up DP - O(n*m*k) time and
O(n) space

იდეა
იდეა მდგომარეობს იმაში, რომ გამოვიყენოთ დინამიკური პროგრამირება bottom-up
მიდგომა , რათა გადავწყვიტოთ, შესაძლებელია თუ არა სტრინგის განაწილება ლექსიკონში
არსებულ სიტყვებად.
შექმენით ბულ ტიპის (boolean) მასივი dp[], სადაც თითოეული ელემენტი dp[i]
აღნიშნავს, შესაძლებელია თუ არა სტრინგის საწყისიდან i პოზიციამდე მდებარე ნაწილის
ლექსიკონში არსებულ სიტყვებად დაყოფა.

ნაბიჯები
1.
2.
3.
4.

დაიწყეთ სტრინგის დასაწყისიდან და მონიშნეთ იგი როგორც სწორი (საბაზისო
შემთხვევა), ანუ: p[0] = true
ყოველი პოზიციისთვის i, შეამოწმეთ, სრულდება თუ არა ლექსიკონის რომელიმე სიტყვა
ამ პოზიციაზე და თან იმყოფება თუ არა მის წინა ნაწილი (dp[j]) უკვე სწორად
განაწილებულ ადგილას.
თუ ასეთი სიტყვა მოიძებნა, მონიშნეთ dp[i] = true, რაც ნიშნავს, რომ s[0:i]
შეიძლება დაიშალოს სწორად.
საბოლოოდ, დააბრუნეთ dp[n] მნიშვნელობა — ეს გვიჩვენებს, შესაძლებელია თუ არა
მთელი სტრინგის სწორად დაყოფა.

სირთულის შეფასება
დროითი სირთულე (Time Complexity):
O(n × m × k) — სადაც:
●

n არის შესამოწმებელი სტრინგის სიგრძე,

●

m არის ლექსიკონში არსებული სიტყვების რაოდენობა,

●

k კი — ლექსიკონში (ყველაზე გრძელი) სიტყვის სიგრძე.

მეხსიერებითი სირთულე (Space Complexity):
O(n) — საჭიროა n - ზომის dp მასივი

გმადლობთ ყურადღებისთვის!

